//1287. 有序数组中出现次数超过25%的元素


#include <vector>
using namespace std;

//一般思路：计数计算
// class Solution {
// public:
//     int findSpecialInteger(vector<int>& arr) {
//         int count = 1;
//         int n = arr.size();
//         for(int i = 1; i < n; i++)
//         {
//             if(arr[i-1] == arr[i])
//             {
//                 count++;
//             }
//             else
//             {
//                 if(count > n*0.25)//当计数超过了25%就返回此元素
//                     return arr[i-1];
//                 else
//                     count = 1;
//             }
//         }
//         //超过25%的可能是最后一个元素
//         if(count > n*0.25)
//             return arr[arr.size()-1];
//         return 0;
//     }
// };


//巧妙思路：先计算出来数组长度的25%，因为数组是非递减的，因此相同数字是相邻的
//当arr[i] == arr[i+len]，返回arr[i]即可
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int len = arr.size() * 0.25;
        int n = arr.size();
        for(int i = 0; i < n-len; i++)//判断条件n-len，防止越界访问
        {
            if(arr[i] == arr[i+len])
                return arr[i];
        }
        return 0;
    }
};